Many video processing techniques apply temporal processing, for example, for temporal predictive coding, temporal noise reduction, de-interlacing, or frame rate conversion. In all these cases, it is advantageous that the temporal information for an area of a current image, for example, a block of pixels in a previous image, used in the processing of the current image, results from the same object, rather than from the same location in the previous image. Hence, it is advantageous to compensate for the relative frame-to-frame motion of the objects in the scene. This so-called motion compensation requires that motion information in video image data can be estimated using a process called motion estimation.
Many motion estimation algorithms used in commercial applications, especially in the consumer domain, are based on a so-called recursive search strategy, where a current motion vector for an area of a current image, for example, for a block of pixels, is determined from only a limited number of previously estimated motion vectors and, optionally, additional (pseudo random) update vectors. This is usually done by: a) calculating a set of temporal and/or spatial candidate motion vectors from the limited number of previously estimated motion vectors and, optionally, the additional (pseudo random) update vectors, wherein spatial candidate motion vectors are based on previously estimated motion vectors in the current image and wherein temporal motion vectors are based on previously estimated motion vectors in a previous image; b) calculating a match error, for example, a block matching error, for respective candidate motion vectors, and; c) selecting the current motion vector from the set of temporal and/or spatial candidate motion vectors by comparing the match errors of the respective candidate motion vectors. One well-known example of such a recursive algorithm is the 3-D recursive search block matching described by G. de Haan et al. in “True-Motion Estimation with 3-D Recursive Search Block Matching”, IEEE Trans. on Circuits and Systems for Video Technology, Vol. 3, No. 5, October 1993, pages 368-379.
Due to their recursive structure, one of the main considerations in the design and application of these motion estimation algorithms is the convergence and accuracy of the calculated motion vector field. This is usually handled by a trade-off between the composition of the set of candidate vectors (for example, the number of candidate vectors for a block of pixels) and the statistical distribution of the update vectors. One can typically increase the speed of the convergence by applying more candidate vectors, though this comes at the expense of a higher computational load. On the other hand, a higher accuracy of the motion vector field can be achieved by using small update vectors, but this also slows down the convergence speed. With many of today's temporally recursive motion estimation algorithms, a good convergence can be obtained after processing a few images, typically in the range of 3 to 5.
In order to provide a good and fast convergence of the motion vector field, motion estimation algorithms that use a temporal recursive structure basically require that the temporal distance between consecutive input images is largely equidistant so that the relative frame-to-frame motion of objects in the scene (caused either by a movement of the objects or by a movement of the camera) is as far as possible constant. However, in some video processing applications, this requirement is not necessarily fulfilled. For example, a wireless video transmission to a mobile device might use a frame rate of 15 Hz, that is, the number of input images transmitted to and processed by the mobile device each second is 15. When the video is derived from a movie source that was originally recorded with 24 images per second, the necessary adaptation of the frame rate might be accomplished by simply skipping individual movie images at the distribution side. The missing images can result in irregular motion patterns in the input image data received by the mobile device. When applying a temporally recursive motion estimation in the mobile device, this can result in a bad convergence of the motion estimation algorithm, resulting in unreliable and inaccurate motion vectors. The application of these motion vectors by further video processing techniques may then result in visible artifacts in the processed images.